package h0808;

import java.util.*;

/**
 * @description 二叉树的广度优先遍历
 * @author 不知名帅哥
 * @date 2024/8/8 12:55
 * @version 1.0
 */
public class BinaryTreeBfs {
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String postOrder = sc.next();
        String inOrder=sc.next();

        TreeNode root = buildTree(postOrder, inOrder);

        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.offerLast(root);
        List<Character> res=new ArrayList<>();
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.removeFirst();
                res.add(currentNode.val);
                if (currentNode.left!=null){
                    queue.offerLast(currentNode.left);
                }
                if (currentNode.right!=null){
                    queue.offerLast(currentNode.right);
                }
            }
        }
        StringBuilder builder = new StringBuilder();
        for (Character c : res) {
            builder.append(c);
        }
        System.out.println(builder);
    }
    public static TreeNode buildTree(String s1,String s2){
        if (s1.isEmpty()||s2.isEmpty()){
            return null;
        }
        return buildTreeHelper(s1.toCharArray(),s2.toCharArray());
    }

    private static TreeNode buildTreeHelper(char[] postOrder, char[] inOrder) {
        //判空情况在上面已经做了
        if (postOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        int len=postOrder.length;
        char rootVal = postOrder[len - 1];
        TreeNode root=new TreeNode(rootVal);

        int mid=0;
        //找到中序遍历二叉树的根节点下标
        for (int i = 0; i < inOrder.length; i++) {
            if (postOrder[len-1]==inOrder[i]){
                mid=i;
                break;
            }
        }
        //构建左子树中序后序遍历
        char[] arrayInLeft = Arrays.copyOfRange(inOrder, 0, mid);
        char[] arrayPostLeft = Arrays.copyOfRange(postOrder, 0, mid);

        //构建右子树中序后序遍历
        char[] arrayInRight=Arrays.copyOfRange(inOrder,mid+1,inOrder.length);
        char[] arrayPostRight=Arrays.copyOfRange(postOrder,mid,len-1);

        root.left=buildTreeHelper(arrayPostLeft,arrayInLeft);
        root.right=buildTreeHelper(arrayPostRight,arrayInRight);
        return root;
    }
}
